package cn.bellychang.leetcode.question046;

import java.util.ArrayList;
import java.util.List;

/**
 * @author ChangLiang
 * @date 2021/3/12
 */
public class Solution2 {

    public List<List<Integer>> permute(int[] nums) {

        List<List<Integer>> result = new ArrayList<>();

        permute(nums, nums.length, nums.length, result);

        return result;
    }

    /**
     *
     * @param nums
     * @param n nums.length
     * @param k k个 k-1个数据的排列问题
     * @param result
     */
    private void permute(int[] nums, int n, int k, List<List<Integer>> result){

        if (k == 1) {
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                list.add(nums[i]);
            }
            result.add(list);
            return;
        }

        for (int i = 0; i < k; i++) {
            // 将子组数中的所有的数分别与第一个数交换，这样就总是在处理后k-1个数的全排列。
            swap(nums, i, k - 1);
            // 这里直接认为下一层返回正确
            permute(nums, n, k-1, result);
            // 需要将nums数组复原
            swap(nums, i, k - 1);
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
